package sjg.tenNormalAlgorithm.divideAndConquer;

/**
 * 分治算法
 * 汉诺塔
 * - 规则: 共三根柱子，将A柱上的盘子[有序]，依旧有序的移动到C柱上。要求：小盘子，不能放到大盘子下面。每次只能移动一个盘子
 */
public class Hanoitowner {
    public static void main(String[] args) {
        hanioTowner(5, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔求解
     * 将 盘子从A柱子上，挪到C柱上。
     */
    private static void hanioTowner(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println("第1个盘从" + a + " -> " + c);
        }else{
            // 盘子数量大于等于2的情况，将其看成，最下面一个盘子，上面的所有盘子，两个实体。
            // 1. 先把上面的所有盘子移动到A->B, 移动过程中会用到C
            hanioTowner(num-1,a,c,b);
            // 2. 最下边的盘 A->C
            System.out.println("第"+num+"个盘从" + a + " -> " + c);
            // 3. 把B塔所有盘 从 B->C, 移动过程使用到A塔
            hanioTowner(num-1,b,a,c);
        }
    }
}
